package common.test;

import common.ListNode;
import common.Node;

public class CopyRandom {

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node curr = head;
        while (curr != null) {
            Node newNode = new Node(curr.val);
            newNode.next = curr.next;
            curr.next = newNode;
            curr = newNode.next;
        }
        Node ans = new Node(0);
        Node tail = ans;
        curr = head;
        while (curr != null) {
            Node random = curr.random;
            tail.next = curr.next;
            if (random != null) {
                tail.random = random.next;
            }
            if (curr.next != null) {
                curr = curr.next.next;
            }
            tail = tail.next;
        }
        return ans.next;
    }
}
